﻿/* 14. Write a program that sorts an array of strings using the quick sort algorithm. */

using System;

public class QuickSortAlgorithm
{
    public static string[] array;
    public static string temp;

    public static void Main()
    {
        DataInput();

        Console.WriteLine("\nArray:");
        PrintArray(array);

        QuickSort(0, array.Length - 1);

        Console.WriteLine("Sorted array:");
        PrintArray(array);
    }

    public static void DataInput()
    {
        int arrayLength;

        do
        {
            Console.Clear();
            Console.Write("\nThe length of array: ");
            if (int.TryParse(Console.ReadLine(), out arrayLength) && (0 < arrayLength))
                break;
        } while (true);

        array = new string[arrayLength];

        Console.WriteLine();
        for (int i = 0; i < arrayLength; i++)
        {
            Console.Write("Array[{0}] = ", i);
            array[i] = Console.ReadLine();
        }
    }

    public static void PrintArray(string[] array)
    {
        Console.Write("{0}", array[0]);
        for (int i = 1; i < array.Length; i++)
            Console.Write(", {0}", array[i]);

        Console.WriteLine("\n");
    }

    public static void QuickSort(int left, int right)
    {
        if (left >= right)
            return;

        int i = left;
        int j = right;
        string k = array[right];

        while (i < j)
        {
            while (i < j && array[i].CompareTo(k) <= 0)
                i++;

            while (i < j && array[j].CompareTo(k) >= 0)
                j--;

            if (i < j)
            {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        temp = array[i];
        array[i] = array[right];
        array[right] = temp;

        QuickSort(left, i - 1);
        QuickSort(i + 1, right);
    }
}